'''
    快速排序
    时间复杂度：最好：O(nlog2(n)) 平均：O(nlog2(n)) 最坏：O(n^2)
    空间复杂度：O(log2(n))~O(n)
    稳定性：不稳定
    复杂性：复杂
    基本思想：每趟排序的结果是比关键字小的在左边，比关键字大的在右边
            1.设置两个变量，i，j，i=0，j=N-1
            2.随机找一个关键字key，一般取第一个或最后一个
            3.从j开始向前搜索，找到第一个小于key的值，将arr[j]和arr[i]进行交换（或者将arr[j]的值赋值给arr[i]）
            4.然后从i开始向后搜索，找到第一个大于key的值，将arr[i]和arr[j]进行交换（或者将arr[i]的值赋值给arr[j]）
            5.重复步骤3和4，直到i==j
            注：如果不是讲arr[i]和arr[j]的值进行交换，最后就得将arr[i]的值等于key的值
            最后递归，结束递归的条件为i>=j
'''

from tool import arr, swp
def quickSort(arr, low, high):
    i = low
    j = high
    if i >= j:
        return arr
    key = arr[low]
    while i < j:
        while i < j and arr[j] >= key:
            j = j - 1
        # arr[i] = arr[j]
        swp(arr,i,j)
        while i < j and arr[i] <= key:
            i = i + 1
        # arr[j] = arr[i]
        swp(arr,i,j)
    # arr[i] = key
    quickSort(arr, low, i - 1)
    quickSort(arr, j + 1, high)
    return arr

if __name__ == '__main__':
    arr1 = [10, 3, 7, 1, 6, 8, 5, 9, 2, 4]
    arr2 = None
    arr = quickSort(arr, 0, len(arr) - 1)
    print(arr)